package top.carrotguo.sorting;

/**
 * 冒泡排序的几种解法
 * @Author: Carrot
 * @Mail: 1053155183carrot@gmail.com
 * @Date: Created in 13:18 2018-05-21
 */
public class Bubble {
    private int[] data;

    public Bubble(int[] data){
        this.data = data;
    }

    /**
     * 传统冒泡排序
     */
    public void BubbleA(){
        int temp;
        for (int i=0; i<data.length; i++) {
            for (int j=0; j<data.length-i-1; j++){
                if (data[j]>data[j+1]) {
                    temp = data[j+1];
                    data[j+1] = data[j];
                    data[j] = temp;
                }
            }
        }
        for (int i=0; i<data.length; i++) {
            System.out.print(data[i]+" ");
        }
    }

    /**
     * 二分查找算法入口(根据查找过程前面序列是否已是排好序来判断是否继续循环遍历)
     */
    public void bubbleB(int lo, int hi){
        while (!sortB(lo,hi--));
        for (int i=0; i<data.length; i++) {
            System.out.print(data[i]+" ");
        }
    }

    /**
     * 二分查找算法入口（根据最后一位逆序位置来遍历它前面的序列，后面的序列是已排序完成）
     */
    public void bubbleC(int lo, int hi){
        while (lo<(hi=sortC(lo,hi)));
        for (int i=0; i<data.length; i++) {
            System.out.print(data[i]+" ");
        }
    }

    /**
     * 执行一次冒泡的内循环 返回单前序列是否有交换过  没交换过即当前序列有序
     * @param lo
     * @param hi
     * @return  是否发送交换动作标志
     */
    private boolean sortB(int lo, int hi){
        boolean sort = true;        //当前序列是否有序标志
        while (++lo<hi) {
            if (data[lo-1]>data[lo]) {
                sort = false;       //当前序列是无序的
                //交换顺序
                int temp = data[lo-1];
                data[lo-1] = data[lo];
                data[lo] = temp;
            }
        }
        return sort;
    }

    /**
     *   执行一次冒泡内部循环，范围是lo~最后一位逆序,后面的序列已是正序且数字比前面的大
     * @return 最后一个交换位置
     */
    private int sortC(int lo, int hi){
        int last = lo;
        while (++lo < hi) {
            if (data[lo-1]>data[lo]) {
                last = lo;              //标记有逆序元素的位置
                int temp = data[lo];
                data[lo] = data[lo-1];
                data[lo-1] = temp;
            }
        }
        return last;
    }

    public static void main(String[] args){
        Bubble bubble = new Bubble(new int[]{5,9,4,1,8,7,22});
        //传统排序方式
        //bubble.BubbleA();

        //根据排序标志控制是否继续遍历方式
        //bubble.bubbleB(0,7);

        //根据最后一位逆序控制遍历范围方式
        bubble.bubbleC(0,7);
    }
}
